package com.xj.algorithm.leetcode;

/**
 * 最长公共前缀
 */
public class L14_多个字符串找最长公共前缀 {

    /**
     *编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     * 示例 1:
     * 输入: ["flower","flow","flight"]
     * 输出: "fl"
     *
     * 示例 2:
     * 输入: ["dog","racecar","car"]
     * 输出: ""
     * 解释: 输入不存在公共前缀。
     * 说明:
     *
     * 所有输入只包含小写字母 a-z 。
     */

    public static void main(String[] args) {
        String[] arr1=new String[]{"flower","flow","flight"};
        String[] arr2=new String[]{"dog","racecar","car"};
        String[] arr3=new String[]{};
        String[] arr4=new String[]{"aa","a"};
        System.out.println(longestCommonPrefixOffice(arr1));
        System.out.println(longestCommonPrefixOffice(arr2));
        System.out.println(longestCommonPrefixOffice(arr3));
        System.out.println(longestCommonPrefixOffice(arr4));
    }

    //自己的解法：找最短字符串，然后两重循环
    public static String longestCommonPrefix(String[] strs) {
        String result="";
        int arrLength=strs.length;
        if(arrLength==0){
            return result;
        }

        //找出长度最小的那个字符串
        int minLength=Integer.MAX_VALUE;
        for(int i=0;i<arrLength;i++){
            int tmpLength=strs[i].length();
            if(tmpLength<minLength){
                minLength=tmpLength;
            }
        }

        for (int i=0;i<minLength;i++){
            //取出第一个字符
            String ch=strs[0].substring(i,i+1);

            //遍历字符数组
            for(int j=0;j<arrLength;j++){
                //取出当前字符串的对应位置的字符
                String tmp=strs[j].substring(i,i+1);
                if(!tmp.equals(ch)){
                    return result;
                }
            }
            result=result+ch;
        }
        return result;
    }


    //官方最优解：水平扫描法，多次比较，关键是indexOf，有现成的方法
    public static String longestCommonPrefixOffice(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++)
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        return prefix;
    }
}
